package LeetCode.Leet700_799.Leet730_739.Leet738;

import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName Solution_2
 * @Author 孙天赐
 * @Date 2025/6/9 7:58
 * @Description TODO: 方法二     贪心  1ms  94.50%
 *                  对方法一的优化，寻找非递增位置的时候，从后往前寻找，找到了也继续向前寻找，就不用递归了
 */
class Solution_2 {
    int[] num;

    public int monotoneIncreasingDigits(int n) {
        if (n == 0) {
            return 0;
        }
        // 整数为int数组，方便求解
        List<Integer> list = new ArrayList<>();
        while (n != 0) {
            list.add(n % 10);
            n = n / 10;
        }
        int len = list.size();
        num = new int[len];
        for (int i = 0; i < len; i++) {
            num[i] = list.get(len - i - 1);
        }

        // 求解
        // 从后往前找单调递减的位置，该位置处元素值减1，并且将该位置后面的元素均置为9，然后继续向前查找
        for (int i = len - 1; i > 0; i--) {
            if (num[i] < num[i - 1]) {
                num[i - 1]--;
                int j = i;
                while (j < len) {
                    num[j++] = 9;
                }
            }
        }

        // 数组转整数
        int result = 0;
        for (int i = 0; i < len; i++) {
            result *= 10;
            result += num[i];
        }

        return result;
    }
}
